import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-05
 * Time: 下午 05:23
 */
public class Test {
    public static int findRoot (int[] elem, int x) {
        while (elem[x] >= 0) x = elem[x];
        return x;
    }
    public static void union (int[] elem, int x1, int x2) {
        int x1Root = findRoot(elem, x1);
        int x2Root = findRoot(elem, x2);
        if (x1Root != x2Root) {
            elem[x1Root] += elem[x2Root];
            elem[x2Root] = x1Root;
        }
    }
    /**
     * 等式的满足性：
     *         给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，
     *     并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字
     *     母变量名。只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
     * 示例 1：
     * 输入：["a==b","b!=a"]
     * 输出：false
     * 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同
     * 时满足这两个方程。
     *
     * 示例 2：
     * 输入：["b==a","a==b"]
     * 输出：true
     * 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
     *
     * 示例 3：
     * 输入：["a==b","b==c","a==c"]
     * 输出：true
     *
     * 示例 4：
     * 输入：["a==b","b!=c","c==a"]
     * 输出：false
     *
     * 示例 5：
     * 输入：["c==c","b==d","x!=z"]
     * 输出：true
     *
     */
    public static boolean equationsPossible(String[] equations) {
        int[] elem = new int[26];
        Arrays.fill(elem, -1);
        for (String x : equations) {
            int x1 = x.charAt(0) - 'a';
            int x2 = x.charAt(3) - 'a';
            if (x.charAt(1) == '=') {
                union(elem, x1, x2);
            }
        }
        for (String x : equations) {
            int x1 = x.charAt(0) - 'a';
            int x2 = x.charAt(3) - 'a';
            if (x.charAt(1) == '!') {
                if (findRoot(elem, x1) == findRoot(elem, x2)) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] arr = {"a==b","b!=a"};
        System.out.println(equationsPossible(arr));
        arr = new String[]{"b==a","a==b"};
        System.out.println(equationsPossible(arr));
        arr = new String[]{"a==b","b==c","a==c"};
        System.out.println(equationsPossible(arr));
        arr = new String[]{"a==b","b!=c","c==a"};
        System.out.println(equationsPossible(arr));
        arr = new String[]{"c==c","b==d","x!=z"};
        System.out.println(equationsPossible(arr));
    }

    /**
     * 邻接矩阵合并
     */
    public static int findCircleNum(int[][] isConnected) {
        int count = 0;
        int[] elem = new int[isConnected.length];
        Arrays.fill(elem, -1);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if (i < j && isConnected[i][j] == 1) {
                    union(elem,i,j);
                }
            }
        }
        for (int x : elem) {
            if (x < 0) count++;
        }
        return count;
    }

    public static void main3(String[] args) {
        int[][] isConnected = {{1,1,1},{1,1,1},{1,1,1}};
        System.out.println(findCircleNum(isConnected));
    }
    public static void main2(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int p = input.nextInt();
        UnionFindSet ufs = new UnionFindSet(n + 1);
        for (int i = 0; i < m; i++) {
            ufs.union(input.nextInt(), input.nextInt());
        }
        for (int i = 0; i < p; i++) {
            if (ufs.isSameSet(input.nextInt(), input.nextInt())) System.out.println("Yes");
            else System.out.println("No");
        }
    }
    public static void main1(String[] args) {
        UnionFindSet ufs = new UnionFindSet(10);
        System.out.println("合并0和6");
        ufs.union(0, 6);
        System.out.println("合并0和7");
        ufs.union(0, 7);
        System.out.println("合并0和8");
        ufs.union(0, 8);
        System.out.println("合并1和4");
        ufs.union(1, 4);
        System.out.println("合并1和9");
        ufs.union(1, 9);
        System.out.println("合并2和3");
        ufs.union(2, 3);
        System.out.println("合并2和5");
        ufs.union(2, 5);
        ufs.show();
        System.out.println("合并1和8");
        ufs.union(1, 8);
        ufs.show();
        System.out.println("判断6和9是否在同一个集合");
        System.out.println(ufs.isSameSet(6, 9));
        System.out.println("判断8和2是否在同一个集合");
        System.out.println(ufs.isSameSet(8, 2));
    }
}
